package hashmap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * 给你一个由 n 个整数组成的数组 nums ，
 * 和一个目标值 target 。请你找出并返回
 * 满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
 * （若两个四元组元素一一对应，则认为两个四元组重复）：
 */
public class LeetCode_18 {
    public static void main(String[] args) {
        int n = 1246018119;
        int count = 0;
        int mid = n / 2;
        for(int i = 1;i <= mid;i++){
            int b = n - i;
            long p = (long)i * b;
            if((p % 3) == 0) count++;
        }
        count *= 2;
        if((n - mid) * mid % 3 == 0 && n % 2 == 0){
            count--;
        }
        System.out.println(count);
//        System.out.println(count);
//        LeetCode_18 leetCode18 = new LeetCode_18();
//        List<List<Integer>> lists = leetCode18.fourSum(new int[]{1000000000,1000000000,1000000000,1000000000}, -1);
//        System.out.println(lists);
    }
    public List<List<Integer>> fourSum(int[] nums, int target) {
        ArrayList<List<Integer>> resultList = new ArrayList<>();
        Arrays.sort(nums);
        for (int left = 0; left < nums.length; left++) {
            if(left > 0 && nums[left] == nums[left - 1]){
                continue;
            }
            int right = nums.length - 1;
            int l = left + 1;
            int r = left + 2;
            while (left < right - 2){
                if(r >= right || l >= r){
                    break;
                }
                Long aLong = Long.valueOf(nums[left]);
                Long bLong = Long.valueOf(nums[l]);
                Long cLong = Long.valueOf(nums[r]);
                Long dLong = Long.valueOf(nums[right]);
                long result = aLong + bLong + cLong + dLong;
                if(result < target){
                    if(r < right - 1){
                        r++;
                    }else if(l < r){
                        l++;
                        r = l + 1;
                    }
                    continue;
                }
                if(result > target){
                    if(l == right - 2){
                        do{
                            right--;
                        }while (right >= 0 && right <= nums.length - 2 && nums[right] == nums[right + 1]);
                        l = left + 1;
                        r = l + 1;
                        continue;
                    }
                    l++;
                    r = l + 1;
                    continue;
                }
                if(result == target){
                    resultList.add(Arrays.asList(nums[left],nums[l],nums[r],nums[right]));
                    do{
                        l++;
                    } while (l < right && nums[l] == nums[l - 1]);
                    r = l + 1;
                }
            }
        }
        return resultList;
    }
}
